class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return findNode( root,  p,  q);

    }
    public TreeNode findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        //先判断根节点是否为p、q节点
        if(root.val == p.val || root.val == q.val) {
            return root;
        }
        //查找左右子树
        TreeNode leftNode = findNode(root.left,p,q);
        TreeNode rightNode = findNode(root.right,p,q);   

        //若左右子树都有返回值，说明祖先就是这个根节点    
        if(leftNode != null && rightNode != null) {
            return root;
        }
        //在左树上找到了
        if(leftNode != null && rightNode == null) {
            return leftNode;
        }
        //在右树上找到了
        if(rightNode != null && leftNode == null) {
            return rightNode;
        }
        return null;
    }
}